package cn.cxq.learning.tree;

import org.junit.jupiter.api.Test;

/**
 * 剑指offer
 * 二叉搜索树的后序遍历序列
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：780749
 * 本题知识点： 栈 树
 * 算法知识视频讲解
 * 题目描述
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）
 * 示例1
 * 输入
 * 复制
 * [4,8,6,12,16,14,10]
 * 返回值
 * 复制
 * true
 */
public class VerifySquenceOfBST {

    boolean flag = true;
//    int count = 0;

    @Test
    public void test() {
        boolean b = VerifySquenceOfBST(new int[]{4, 8, 6, 12, 16, 14, 10});
        System.out.println(b);
    }

    public boolean VerifySquenceOfBST(int[] sequence) {

        if (sequence.length == 0) {
            return false;
        }

        bst(sequence, 0, sequence.length - 1);

        return flag;
    }

    // 思路：因为是二叉排序树，而且是后序遍历，
    // 那么就按照根，左子树右子树递归的顺序判断每个树的左子树是否都小于根，右子树是否都大于根。
    private void bst(int[] sequence, int leftBound, int rightBound) {

        if (leftBound < rightBound) {
            int root = sequence[rightBound];

            int index;
            for (index = leftBound; index < rightBound; index++) {
                if (sequence[index] > root) {
                    break;
                }
            }

            int mid = index - 1;

            while (index < rightBound) {
                if (sequence[index] < root) {
                    flag = false;
                    break;
                }
                index++;
            }

            if (flag) {
                bst(sequence, leftBound, mid);
                bst(sequence, mid + 1, rightBound - 1);
            }
        }

    }

    // 投机取巧。。
//    // 思路： 先从最后一个节点开始遍历生成二叉搜索树，
//    // 然后后序遍历该树看看是不是符合原数组的顺序，如果符合返回true，否则返回false。
//    public boolean VerifySquenceOfBST(int[] sequence) {
//
//        if (sequence.length == 0) {
//            return false;
//        }
//
//        TreeNode root = new TreeNode(sequence[sequence.length - 1]);
//
//        for (int i = sequence.length - 1; i >= 0; i--) {
//            addSortTreeNode(root, sequence[i]);
//        }
//
//        preorderTransversal(root, sequence);
//
//        return flag;
//    }
//
//    private void preorderTransversal(TreeNode node, int[] sequence) {
//
//        if (!flag) {
//            return;
//        }
//
//        if (node.left != null) {
//            preorderTransversal(node.left, sequence);
//        }
//
//        if (node.right != null) {
//            preorderTransversal(node.right, sequence);
//        }
//
//        if (sequence[count] != node.val) {
//            flag = false;
//        } else {
//            count++;
//        }
//    }
//
//    private void addSortTreeNode(TreeNode node, int value) {
//
//        if (node.val > value) {
//            if (node.left == null) {
//                node.left = new TreeNode(value);
//            } else {
//                addSortTreeNode(node.left, value);
//            }
//        }
//
//        if (node.val < value) {
//            if (node.right == null) {
//                node.right = new TreeNode(value);
//            } else {
//                addSortTreeNode(node.right, value);
//            }
//        }
//    }
}
